#include <iostream>
#include <stdlib.h>

using namespace std;


template <typename T>
class Node
{
public:
	Node(T _val, Node* _next = nullptr)
	{
		val = _val;
		next = _next;
	}

	T   val;
	Node* next;
};

template <typename T>
__interface IEnumerable
{
	virtual T	  First();
	virtual void  Next();
	virtual T     Current() const;
	virtual bool  isDone()  const;
};

template <typename T> class LinkedList;
template <typename T> LinkedList<T> operator<<(LinkedList<T>&, T);

template <typename T>
class LinkedList : public IEnumerable<Node<T>*>
{
public:
	LinkedList();
	~LinkedList();

	void Insert		(const T& val);
	void InsertFirst(const T& val);
	T    RemoveFirst();
	T	 Remove		(const T& val);
	void Clear		();
	void PrintList	();

	//		   @overrides
	virtual Node<T>*	First();
	virtual void		Next();
	virtual Node<T>*	Current() const;
	virtual bool		isDone()  const;

	friend LinkedList<T> &operator<<(LinkedList<T> & li, T val)
	{
		li.Insert(val);
		return li;
	}

private:
	Node<T>*	head;
	Node<T>*	last;
	Node<T>*	current;
	bool		underTraversal;
	bool		done;

};


template <typename T>
LinkedList<T>::LinkedList()
{
	head = new Node<T>(0);
	last = head;
}

template <typename T>
LinkedList<T>::~LinkedList()
{
	Clear();
}

template <typename T>
void LinkedList<T>::Clear()
{
	Node<T>* temp = head;
	current = temp;
	while(current != nullptr)
	{
		temp = current;
		delete temp;
		current = current->next;
	}
}

template <typename T>
void LinkedList<T>::PrintList()
{
	for ( Node<T>* current = First(); !isDone(); Next() )
	{
		current = Current();
		cout << current->val << endl;
	}
	
}

template <typename T>
void LinkedList<T>::Insert(const T& val)
{
	last->next = new Node<T>(val);
	last = last->next;
}

template <typename T>
T LinkedList<T>::RemoveFirst()
{
	if (head->next == nullptr)
		return nullptr;

	Node<T>* temp = head->next;
	T val = temp->val;
	head->next = temp->next;
	delete temp;

	return val;
}

template <typename T>
void LinkedList<T>::InsertFirst(const T& val)
{
	Node<T>* temp = head->next;
	Node<T>* newNode = new Node<T>(val);

	if ( temp == nullptr )
	{
		head->next = newNode;
	}
	else
	{
		head->next = newNode;
		newNode->next = temp;
	}
}

// Not working
template <typename T>
LinkedList<T> &operator<<(LinkedList<T> &li, T val)
{
	li.Insert(val);
	return li;
}

template <typename T>
Node<T>* LinkedList<T>::First()
{
	underTraversal = true;
	current = head->next;
	done = current == nullptr;
	return current;
}

template <typename T>
void LinkedList<T>::Next()
{
	current = current -> next;
	if ( current == nullptr )
	{
		underTraversal = false;
		done = true;
	}
}

template <typename T>
bool LinkedList<T>::isDone() const
{
	return done;
}

template <typename T>
Node<T>* LinkedList<T>::Current() const
{
	if (underTraversal)
		return current;

	else
		return nullptr;
}


